package RKUjava.datastructures;
import java.util.Enumeration;
import java.io.Serializable;
import java.util.NoSuchElementException;

/** RKUDoubleChain implements a double connected list. 
    The linking is done in the stored objects by implementing the 
    RKUDoubleChainLink interface. If you want to store non-extendable objects
    in the double chain you can do this by using the RKUDoubleChainWrapper 
    which acts as a wrapper around the object. This wrapper should also be used
    if you intend to store the object in more than one RKUDoubleChain.<br>
    The naming of methods resembles the Vector class as much as possible. 
    This should make
    it somewhat easier to switch between the two datastructures.<br><br>
    <b>Note:</b> All objects stored must implement the RKUDoubleChainLink 
    interface. If you don't implement the interface the objects will be wrapped
    in a RKUDoubleChainWrapper object. A disadvantage of implementing the
    interface is that the object can only be stored in one double chained list.

    @see RKUDoubleChainLink
    @see RKUDoubleChainWrapper

*/
public class RKUDoubleChain implements Enumeration, Serializable
{
    /**
    @serial
    */
  protected Object firstlink, lastlink, curlink;
    /**
    @serial
    */
  protected boolean direction;
    /**
    @serial
    */
  protected int elementCount;

  public RKUDoubleChain()
    {
      super();
      firstlink = null;
      lastlink = null;
    }

  /** Copies the components of this double chain into the specified array.
      The array must be big enough to hold all the objects on this chain.
      If the objects are stored with the RKUDoubleChainWrapper class then
      they are extracted from this wrapper and stored in the array.
      @param anArray the array into which the components get copied.
  */
  public synchronized void copyInto(Object anArray[])
    {
      Object curobj;
      int index;

      curobj = firstlink;
      index = 0;

      while(curobj!=null) {

	if (curobj instanceof RKUDoubleChainWrapper)
	  anArray[index] = ((RKUDoubleChainWrapper)curobj).theobject;
	else
	  anArray[index] = curobj;

	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	index++;
      }
    }

  /** Copies the components of this double chain into the specified array in 
      reversed order. This is implemented by starting at the last object and
      following the prev pointer.
      The array must be big enough to hold all the objects on this chain.
      If the objects are stored with the RKUDoubleChainWrapper class then
      they are extracted from this wrapper and stored in the array.
      @param anArray the array into which the components get copied.
  */
  public synchronized void copyIntoReversed(Object anArray[])
    {
      Object curobj;
      int index;

      curobj = lastlink;
      index = 0;

      while(curobj!=null) {

	if (curobj instanceof RKUDoubleChainWrapper)
	  anArray[index] = ((RKUDoubleChainWrapper)curobj).theobject;
	else
	  anArray[index] = curobj;

	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();
	index++;
      }
    }

  /** Trims the capacity of this double chain to be the current size.
      This method has no functionality but is implemented to make the
      use of the RKUDoubleChain compatible with RKUVector (and Suns Vector)
  */
  public synchronized void trimToSize()
    {
    }

  /** Increases the capacity of this double chain.
      This method has no functionality but is implemented to make the
      use of the RKUDoubleChain compatible with RKUVector (and Suns Vector)
      @param minCapacity the desired minimal capacity.
  */
  public synchronized void ensureCapacity(int minCapacity)
    {
    }

  /** Sets the size of this double chain. If the new size is greater than 
      the current size, new RKUDoubleChainWrapper objects carrying null 
      items are added to the end of the double chain. If the new size is 
      less than the current size, all components at index newSize 
      and greater are discarded. <br>
      <blink>NOT IMPLEMENTED YET!</blink>
      @param newSize the new size of this double chain.
  */
  public synchronized void setSize(int newSize)
    {
    }

  /** Returns the current capacity of this double chain. This is the same as
      size.      
      @return the current capacity of this double chain. 
  */
  public int capacity()
    {
      return elementCount;
    }

  /** Returns the number of components in this double chain. This is the same
      as the capacity. 
      @return the number of components in this double chain. 
  */
  public int size()
    {
      return elementCount;
    }

  /** Tests if this double chain has no components. 
      @return true if this double chain has no components; false otherwise. 
  */
  public boolean isEmpty()
    {
      return (elementCount == 0);
    }

  /** Returns an enumeration of the components of this double chain.
      Since the RKUDoubleChain implements the Enumeration interface 
      it resets its index and return a pointer to itself.
      @return an enumeration of the components of this 
      @see RKUEnumeration 
  */
  public synchronized Enumeration elements()
    {
      curlink = firstlink;
      direction = true; // true means advance via the next pointer
      return this;
    }

  /** Returns an enumeration of the components of this double chain in 
      reversed order.
      Since the RKUDoubleChain implements the Enumeration interface 
      it resets its index and return a pointer to itself.
      @return an enumeration of the components of this 
      @see RKUEnumeration 
  */
  public synchronized Enumeration elementsReversed()
    {
      curlink = lastlink;
      direction = false; // true means advance via the next pointer
      return this;
    }

  /** Tests if the specified object is a component in this double chain. <br>
      Time: O(n)
      @param elem an object. 
      @return true if the specified object is a component in this double 
      chain; false otherwise.
  */
  public boolean contains(Object elem)
    {
      return (indexOf(elem)!=-1);
    }

  /** Searches for the first occurence of the given argument, testing for 
      equality using the equals method. 
      @param elem an object. 
      @return the index of the first occurrence of the argument in this 
      double chain; returns -1 if the object is not found. 
  */
  public int indexOf(Object elem)
    {
      Object curobj;
      int index;

      curobj = firstlink;
      index = 0;

      while(curobj!=null) {

	if (curobj instanceof RKUDoubleChainWrapper) {
	  if (((RKUDoubleChainWrapper)curobj).theobject.equals(elem))
	    return index;
	}
	else {
	  if (((RKUDoubleChainWrapper)curobj).equals(elem))
	    return index;
	}
	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	index++;
      }
      return -1;
    }


  /** Searches for the first occurence of the given argument, 
      beginning the search at index, and testing for equality using 
      the equals method. 
      @param elem an object. 
      @param index the index to start searching from. 
      @return the index of the first occurrence of the object argument in 
      this double chain at position index or later in the chain; 
      returns -1 if the object is not found. 
  */
  public synchronized int indexOf(Object elem, int index)
    {
      Object curobj;
      int i;

      curobj = firstlink;
      i = 0;

      while (curobj!=null && index>0) {
	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	index--;
	i++;
      }

      if (curobj==null)
	return -1;

      while(curobj!=null) {

	if (curobj instanceof RKUDoubleChainWrapper) {
	  if (((RKUDoubleChainWrapper)curobj).theobject.equals(elem))
	    return i;
	}
	else {
	  if (((RKUDoubleChainWrapper)curobj).equals(elem))
	    return i;
	}
	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	i++;
      }
      return -1;
    }

  /** Searches for the last occurence of the given argument, testing for 
      equality using the equals method. 
      @param elem an object. 
      @return the index of the lasst occurrence of the argument in this 
      double chain; returns -1 if the object is not found. 
  */
  public int lastIndexOf(Object elem)
    {
      Object curobj;
      int index;

      curobj = lastlink;
      index = 0;

      while(curobj!=null) {

	if (curobj instanceof RKUDoubleChainWrapper) {
	  if (((RKUDoubleChainWrapper)curobj).theobject.equals(elem))
	    return index;
	}
	else {
	  if (((RKUDoubleChainWrapper)curobj).equals(elem))
	    return index;
	}
	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();
	index++;
      }
      return -1;
    }


  /** Searches for the last occurence of the given argument, 
      beginning the search at index, and testing for equality using 
      the equals method. 
      @param elem an object. 
      @param index the index to start searching from. 
      @return the index of the last occurrence of the object argument in 
      this double chain at position index or later in the chain; 
      returns -1 if the object is not found. 
  */
  public synchronized int lastIndexOf(Object elem, int index)
    {
      Object curobj;
      int i, j;

      curobj = lastlink;
      i = elementCount-1;

      j = elementCount-index-1;

      while (curobj!=null && j>0) {
	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();
	j--;
	i--;
      }

      if (curobj==null)
	return -1;

      while(curobj!=null) {

	if (curobj instanceof RKUDoubleChainWrapper) {
	  if (((RKUDoubleChainWrapper)curobj).theobject.equals(elem))
	    return i;
	}
	else {
	  if (((RKUDoubleChainWrapper)curobj).equals(elem))
	    return i;
	}
	curobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();
	i--;
      }
      return -1;
    }

  
  /** Returns the component at the specified index. 
      Even though the double chain is not kept in an array it still throws
      ArrayIndexOutOfBoundsException, which is to ensure compatibility with
      the Vector class.
      @param index an index into this double chain.
      @return the component at the specified index. 
      @exception ArrayIndexOutOfBoundsException if an invalid index was given. 
  */
  public synchronized Object elementAt(int index)
    {
      if (index<0 || index>=elementCount)
	throw new ArrayIndexOutOfBoundsException("Cannot return object with index="+index+". It must be between 0 and "+(elementCount-1)+" (both included)");
      else {
	Object curobj;
	curobj = firstlink;
	while (curobj!=null && index>0) {
	  curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	  index--;
	}
	if (curobj instanceof RKUDoubleChainWrapper)
	  return ((RKUDoubleChainWrapper)curobj).theobject;
	else
	  return curobj;
      }
    }

  /** Returns the (wrapped) component at the specified index. 
      This is semilar to elementAt except that it return the wrapped 
      object. If your stored object implements the RKUDoubleChainLink interface
      there is no difference.<br>
      The wrapped object is sometimes useful for inserting in the 
      middle of the chain. <br>
      Even though the double chain is not kept in an array it still throws
      ArrayIndexOutOfBoundsException, which is to ensure compatibility with
      the Vector class.
      @param index an index into this double chain.
      @return the component at the specified index. 
      @exception ArrayIndexOutOfBoundsException if an invalid index was given. 
  */

  public synchronized Object wrappedElementAt(int index)
    {
      if (index<0 || index>=elementCount)
	throw new ArrayIndexOutOfBoundsException("Cannot return object with index="+index+". It must be between 0 and "+(elementCount-1)+" (both included)");
      else {
	Object curobj;
	curobj = firstlink;
	while (curobj!=null && index>0) {
	  curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	  index--;
	}
	return curobj;
      }
    }


  /** Returns the first component of this double chain. 
      @return the first component of this double chain. 
      @exception NoSuchElementException if this double chain has no components. 
  */
  public synchronized Object firstElement()
    {
      if (elementCount==0)
	throw new NoSuchElementException("The double chain is empty.");
      else
	return firstlink;
    }

  /** Returns the last component of this double chain. 
      @return the last component of this double chain. 
      @exception NoSuchElementException if this double chain has no 
      components.
  */
  public synchronized Object lastElement()
    {
      if (elementCount==0)
	throw new NoSuchElementException("The double chain is empty.");
      else
	return lastlink;
    }

  /** Sets the component at the specified index of this double chain to be 
      the specified object. The previous component at that position 
      is discarded. The index must be a value greater than or equal 
      to 0 and less than the current size of the double chain. 
      @param obj what the component is to be set to. 
      @param index the specified index. 
      @exception ArrayIndexOutOfBoundsException if the index was invalid. 
  */
  public synchronized void setElementAt(Object obj, int index)
    {
      if (index<0 || index>=elementCount)
	throw new ArrayIndexOutOfBoundsException("Cannot set object with index="+index+". It must be between 0 and "+(elementCount-1)+" (both included)");
      else {
	Object curobj = wrappedElementAt(index);

	if (curobj instanceof RKUDoubleChainWrapper) {
	  ((RKUDoubleChainWrapper)curobj).theobject = obj;
	}
	else {
	  Object nextobj, prevobj;
	  nextobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	  prevobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();
	  
	  ((RKUDoubleChainLink)obj).setDoubleChainNext(nextobj);
	  ((RKUDoubleChainLink)obj).setDoubleChainPrev(prevobj);

	  if (nextobj!=null) {
	    ((RKUDoubleChainLink)nextobj).setDoubleChainPrev(obj);
	  }
	  else {
	    lastlink = obj;
	  }
	
	  if (prevobj!=null) {
	    ((RKUDoubleChainLink)prevobj).setDoubleChainNext(obj);
	  }
	  else {
	    firstlink = obj;
	  }

	  ((RKUDoubleChainLink)curobj).setDoubleChainNext(null);
	  ((RKUDoubleChainLink)curobj).setDoubleChainPrev(null);
	}
      }
    }

  /** Deletes the component at the specified index. Each component in 
      this double chain with an index greater or equal to the specified 
      index is shifted downward to have an index one smaller than 
      the value it had previously. <br><br>
      The index must be a value greater than or equal to 0 and less
      than the current size of the double chain.

      @param index the index of the object to remove. 
      @exception ArrayIndexOutOfBoundsException if the index was invalid. 
  */
  public synchronized void removeElementAt(int index)
    {
      if (index<0 || index>=elementCount)
	throw new ArrayIndexOutOfBoundsException("Cannot remove object with index="+index+". It must be between 0 and "+(elementCount-1)+" (both included)");
      else {
	Object curobj = wrappedElementAt(index);
	Object nextobj, prevobj;
	nextobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	prevobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();

	if (nextobj!=null) {
	  ((RKUDoubleChainLink)nextobj).setDoubleChainPrev(prevobj);
	}
	else {
	  lastlink = prevobj;
	}
	
	if (prevobj!=null) {
	  ((RKUDoubleChainLink)prevobj).setDoubleChainNext(nextobj);
	}
	else {
	  firstlink = nextobj;
	}
	
	((RKUDoubleChainLink)curobj).setDoubleChainNext(null);
	((RKUDoubleChainLink)curobj).setDoubleChainPrev(null);
	elementCount--;
      }
    }

  /** Inserts the specified object as a component in this double chain at the 
      specified index. Each component in this double chain with an index 
      greater or equal to the specified index is shifted upward to 
      have an index one greater than the value it had previously. <br><br>
      The index must be a value greater than or equal to 0 and less 
      than or equal to the current size of the double chain. 
      @param obj the component to insert. 
      @param index where to insert the new component. 
      @exception ArrayIndexOutOfBoundsException if the index was invalid. 
  */
  public synchronized void insertElementAt(Object obj, int index)
    {
      if (index>elementCount || index<0)
	throw new ArrayIndexOutOfBoundsException("Cannot insert object with index="+index+". It must be between 0 and "+elementCount+" (both included)");
      else {
	Object curobj;
	Object newobj = wrapObject(obj);
	Object nextobj, prevobj;

	if (index==elementCount) {
	  // Insert as last element.
	  if (elementCount>0)
	    ((RKUDoubleChainLink)lastlink).setDoubleChainNext(newobj);
	  ((RKUDoubleChainLink)newobj).setDoubleChainPrev(lastlink);
	  lastlink = newobj;
	}
	else {
	  curobj = wrappedElementAt(index);

	  // Insert somewhere in the middle.
	  nextobj = curobj;
	  prevobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();

	  ((RKUDoubleChainLink)newobj).setDoubleChainNext(nextobj);
	  ((RKUDoubleChainLink)newobj).setDoubleChainPrev(prevobj);

	  ((RKUDoubleChainLink)nextobj).setDoubleChainPrev(newobj);
	
	  if (prevobj!=null) {
	    ((RKUDoubleChainLink)prevobj).setDoubleChainNext(newobj);
	  }
	  else {
	    firstlink = newobj;
	  }
	}
	elementCount++;
      }
    }

  /** Adds the specified component to the end of this double chain,
      increasing its size by one. The capacity of this double chain is
      increased if its size becomes greater than its capacity. <br>
      Time: O(1)
      @param obj the component to be added. 
  */
  public synchronized void addElement(Object obj)
  {
    obj = wrapObject(obj);
    if (firstlink==null) {
      firstlink = obj;
      lastlink = obj;
      ((RKUDoubleChainLink)obj).setDoubleChainNext(null);
      ((RKUDoubleChainLink)obj).setDoubleChainPrev(null);
    }
    else {
      ((RKUDoubleChainLink)obj).setDoubleChainNext(null);
      ((RKUDoubleChainLink)obj).setDoubleChainPrev(lastlink);
      ((RKUDoubleChainLink)lastlink).setDoubleChainNext(obj);
      lastlink = obj;
    }
    elementCount++;
  }

  /** Removes the first occurrence of the argument from this double chain. If the
      object is found in this double chain, each component in the double chain with an
      index greater or equal to the object's index is shifted downward to
      have an index one smaller than the value it had previously. 

      @param obj the component to be removed. 
      @return true if the argument was a component of this double chain; false
      otherwise. 
  */
  public synchronized boolean removeElement(Object obj)
  {
    Object curobj;
    Object nextobj, prevobj;
    int index;

    if (obj instanceof RKUDoubleChainLink) {

      nextobj = ((RKUDoubleChainLink)obj).getDoubleChainNext();
      prevobj = ((RKUDoubleChainLink)obj).getDoubleChainPrev();

      if (nextobj!=null) {
	((RKUDoubleChainLink)nextobj).setDoubleChainPrev(prevobj);
      }
      else {
	lastlink = prevobj;
      }
      
      if (prevobj!=null) {
	((RKUDoubleChainLink)prevobj).setDoubleChainNext(nextobj);
      }
      else {
	firstlink = nextobj;
      }
	
      ((RKUDoubleChainLink)obj).setDoubleChainNext(null);
      ((RKUDoubleChainLink)obj).setDoubleChainPrev(null);
      
      elementCount--;
      return true;
    }
    else {
      boolean done=false;
      curobj = firstlink;

      while(curobj!=null && !done) {

	if (curobj instanceof RKUDoubleChainWrapper) {
	  if (((RKUDoubleChainWrapper)curobj).theobject.equals(obj))
	    done = true;
	  else
	    curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	}
	else {
	  if (((RKUDoubleChainWrapper)curobj).equals(obj))
	    done = true;
	  else
	    curobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
	}
      }
      if (curobj==null)
	return false;

      nextobj = ((RKUDoubleChainLink)curobj).getDoubleChainNext();
      prevobj = ((RKUDoubleChainLink)curobj).getDoubleChainPrev();

      if (nextobj!=null) {
	((RKUDoubleChainLink)nextobj).setDoubleChainPrev(prevobj);
      }
      else {
	lastlink = prevobj;
      }
      
      if (prevobj!=null) {
	((RKUDoubleChainLink)prevobj).setDoubleChainNext(nextobj);
      }
      else {
	firstlink = nextobj;
      }
	
      ((RKUDoubleChainLink)curobj).setDoubleChainNext(null);
      ((RKUDoubleChainLink)curobj).setDoubleChainPrev(null);
      
      elementCount--;
      return true;
    }
  }

  /** Removes all components from this double chain and sets its size to zero. 
   */
  public synchronized void removeAllElements()
    {
      elementCount = 0;
      lastlink = null;
      firstlink = null;
    }


  /** Removes all components from this double chain and sets its size to zero. 
      This method does exactly the same as removeAllElements().
   */
  public synchronized void removeAllElementsFast()
    {
      removeAllElements();
    }

  /** Returns a clone of this double chain. 
      <blink> NOT IMPLEMENTED YET!</blink> 
  */
  public synchronized Object clone()
    {
      return null;
    }

  /** Returns a string representation of this double chain. 
      @return a string representation of this double chain. 
  */
  public synchronized String toString()
    {
      return super.toString();
    }

  /** Implementation of the Enumeration interface. */
  public boolean hasMoreElements()
    {
      return (curlink!=null);
    }

  /** Implementation of the Enumeration interface. */
  public Object nextElement()
    {
      Object res = curlink;
      if (direction)
	curlink = ((RKUDoubleChainLink)curlink).getDoubleChainNext();
      else
	curlink = ((RKUDoubleChainLink)curlink).getDoubleChainPrev();

      if (res instanceof RKUDoubleChainWrapper)
	return ((RKUDoubleChainWrapper)res).theobject;
      else
	return res;
    }

  /** Wrap an object if nessecary. */
  private Object wrapObject(Object obj)
    {
      if (obj instanceof RKUDoubleChainLink)
	return obj;
      else
	return new RKUDoubleChainWrapper(obj);
    }

}
